package com.ocean.array;

/**
 * https://leetcode.cn/problems/climbing-stairs/
 */
public class ClimbStairs3 {


    public static void main(String[] args) {
        System.out.println(new ClimbStairs3().climbStairs2(2));
        System.out.println(new ClimbStairs3().climbStairs2(3));
        System.out.println(new ClimbStairs3().climbStairs2(4));
        System.out.println(new ClimbStairs3().climbStairs2(5));
        System.out.println(new ClimbStairs3().climbStairs2(6));
        System.out.println(new ClimbStairs3().climbStairs2(7));
    }


    public int climbStairs(int n) {
        return 1;
    }


    public int climbStairs2(int n) {
        if (n == 1 || n == 0) {
            return 1;
        }
        int cur = 1;
        int pre = 1;
        for (int i = 2; i <= n; i++) {
            int temp = cur + pre;
            pre = cur;
            cur = temp;
        }
        return cur;
    }

    public int climbStairs3(int n) {
        if (n == 1 || n == 0) {
            return 1;
        }
        int[] db = new int[n + 1];
        db[0] = 1;
        db[1] = 1;
        for (int i = 2; i <= n; i++) {
            db[i] = db[i - 1] + db[i - 2];
        }
        return db[n];
    }


    public int climbStairs4(int n) {
        if (n == 1 || n == 0) {
            return 1;
        }
        return climbStairs4(n - 1) + climbStairs4(n - 2);
    }

}
